//
// Created by LiuYou on 2021/5/24.
//

#include <unordered_map>
#include <cstdlib>
#include <iostream>
#include <vector>
#include <climits>

static std::pair<std::string, int>
findLowestCostNode(std::__umap_hashtable<std::string, int>& costs, std::vector<std::pair<std::string, int>>& processed);

static void DijkstraAlgorithm(std::__umap_hashtable<std::string, std::__umap_hashtable<std::string, int>>& graph,
                              std::__umap_hashtable<std::string, int>& costs,
                              std::__umap_hashtable<std::string, std::string>& parent,
                              std::vector<std::pair<std::string, int>>& processed);

/**
 * @brief 还是有问题, 见 03 。
 * @return
 */
int main() {
    // 使用散列表存储邻居和前往邻居的开销
    std::__umap_hashtable<std::string, std::__umap_hashtable<std::string, int>> graph;
    graph["start"] = {};
    graph["start"]["a"] = 6;
    graph["start"]["b"] = 2;

    std::cout << graph["start"]["a"] << std::endl;
    std::cout << graph["start"]["b"] << std::endl;

    graph["a"] = {};
    graph["a"]["final"] = 1;
    graph["b"] = {};
    graph["b"]["a"] = 3;
    graph["b"]["final"] = 5;
    graph["final"] = {};

    // 使用散列表存储每个结点的开销
    std::__umap_hashtable<std::string, int> costs;
    costs["a"] = 6;
    costs["b"] = 2;
    // py中可以表示无穷大, 但是C++中设置一个标志数即可。这里我设置成了 -1 。
    // 不行, 这里不能设置为 -1 , 因为后续操作算法要对cost哈希表中的元素比较大小！！！！
    costs["final"] = INT_MAX;

    // 还需要一个散列表, 这个散列表存储父结点
    std::__umap_hashtable<std::string, std::string> parent;
    parent["a"] = "start";
    parent["b"] = "start";
    parent["final"] = "";

    // 还需要一个数组来记录处理过的结点。
    std::vector<std::pair<std::string, int>> processed;

    // Dijkstra算法。
    DijkstraAlgorithm(graph, costs, parent, processed);

    for (const auto& item : parent) {
        std::cout << item.second << std::endl;
    }


    std::exit(0);
}

static void
DijkstraAlgorithm(std::__umap_hashtable<std::string, std::__umap_hashtable<std::string, int>>& graph,
                  std::__umap_hashtable<std::string, int>& costs,
                  std::__umap_hashtable<std::string, std::string>& parent,
                  std::vector<std::pair<std::string, int>>& processed) {
//     下面实现狄克斯特拉算法
//    const std::pair<std::string, int>& lowestCostNode = findLowestCostNode(costs);
    std::pair<std::string, int> lowestCostNode = findLowestCostNode(costs, processed);

    while (lowestCostNode != std::pair<std::string, int>()) {
        // 获取该结点的开销
        std::pair<std::string, int> cost = *costs.find(lowestCostNode.first);
        // 获取该结点的邻居
        std::__umap_hashtable<std::string, int> neighbors = graph[lowestCostNode.first];
        for (const auto& item : neighbors) {
            std::pair<std::string, int> newCost(cost.first, cost.second + item.second);

            // TODO 注意:
            if (costs[item.first] > newCost.second) {
                costs[item.first] = newCost.second;
                // TODO 注意: 通过调试得出结论: 这里代码写错了！！！！
//                parent[item.first] = std::to_string(lowestCostNode.second);
                parent[item.first] = lowestCostNode.first;

            }
        }

        // TODO 注意: 原因终于终于终于找出来了, 原因是: 这里虽然加入到了 processed数组中, 但是在进行
        //  下面的 findLowestCostNode()函数时, 依然会返回一样的结果。使上面的for循环一直重复！！！！
        processed.push_back(lowestCostNode);
//        const std::pair<std::string, int>& node = findLowestCostNode(costs);
        std::pair<std::string, int> node = findLowestCostNode(costs, processed);
    }
}

static std::pair<std::string, int>
findLowestCostNode(std::__umap_hashtable<std::string, int>& costs,
                   std::vector<std::pair<std::string, int>>& processed) {
    std::pair<std::string, int> node = *costs.cbegin();
    for (const auto& item : costs) {
        for (const auto& elem : processed) {
            if (item.first == elem.first) {
                break;
            } else {
                if (item.second < node.second) {
                    node = item;
                }
            }
        }
    }
    return node;
}
